#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

// COMPILE: gcc -o cs -lm check-solution.c

typedef struct _node {
    int number;
    struct _node *next;
} node;

typedef struct {
    int from, to;
} path_link;

typedef struct _coord
{
//    int number;
    double x, y;
} coord;

//------------------------------------------------------------------------------

int node_list_to_path(int n_nodes, node *list, path_link **path)
{
    node *nd;
    int n_path_links;
    int i;
    if (n_nodes % 2 != 0) {
        fprintf(stderr, "n_nodes is not even\n");
        exit(0);
    }
    n_path_links = n_nodes;
    *path = (path_link *) malloc(n_path_links*sizeof(path_link));
    if (NULL == *path) {
        fprintf(stderr, "Memory overflow\n");
        exit(0);
    }
    /* Adjusted so we can deal with non-cycles */
    for (i = 0, nd = list; /* nd->next != NULL */; (nd = nd->next), (i += 1)) {
        (*path)[i].from = nd->number;
        if( NULL == nd->next ){  (*path)[i].to = -1;  break;  }
        (*path)[i].to = nd->next->number;
    }
    return n_path_links;        
}

//------------------------------------------------------------------------------

// Returnz:
// 0 -> yes,
// bit 0 set -> not all nodes covered,
// bit 1 set -> some nodes visited more than once,
// bit 2 set -> node visited whose number is > path_size
int is_hamiltonian(int path_size, path_link p[])
{
    int *node_visit_count;
    int i, from, to;
    int err_bits = 0;
//    int last_to;
    if (NULL == (node_visit_count = (int *) malloc(path_size*sizeof(int)))) {
        fprintf(stderr, "Memory overflow\n");
        exit(0);
    }
    memset(node_visit_count, 0, path_size*sizeof(int));
    for (i = 0; i < path_size; ++i) {
        from = p[i].from;
        to = p[i].to;
        if (from >= path_size) {
            err_bits |= 1 << 2;
        } else {
            node_visit_count[from] += 1;
        }
    }
/* Not using cycles.
    last_to = p[path_size - 1].to;
    if (last_to >= path_size) {
        err_bits |= 1 << 2;
    } else {
        node_visit_count[last_to] += 1;
    }
*/
    for (i = 0; i < path_size; ++i) {
        if (node_visit_count[i] > 1) {
            err_bits |= 1 << 1;

            fprintf( stderr, "Node %d visited %d times.\n", i, node_visit_count[i] );

        } else if (node_visit_count[i] == 0) {
            err_bits |= 1;

            fprintf( stderr, "Node %d unvisited.\n", i );

        }
    }
    free(node_visit_count);
    return err_bits;   
}

//------------------------------------------------------------------------------

int compare_path_links_for_sort(const void *p1, const void *p2)
{
    return ((path_link *) p1)->from - ((path_link *) p2)->from;
}    

//------------------------------------------------------------------------------

void sort_path_on_from(int path_size, path_link *p)
{
    qsort(p, path_size, sizeof(path_link), compare_path_links_for_sort);
}    

//------------------------------------------------------------------------------

int read_paths(char *filename, node **path1, node **path2)
{
    FILE *fin = fopen(filename, "r");
    node *curr_node1 = NULL, *prev_node1 = NULL,
         *curr_node2 = NULL, *prev_node2 = NULL;
    int number1, number2;
    char junk[256];
    int n_nodes = 0;
    if (NULL == fin) {
        fprintf(stderr, "Unable to open %s\n", filename);
        exit(0);
    }
    fgets(junk, 255, fin);  // skip header
    while (!feof(fin)) {
        if (fscanf(fin, "%d,%d", &number1, &number2) < 2) {
            fclose(fin);
            break;
        }
        if (NULL == (curr_node1 = (node *) malloc(sizeof(node)))) {
            fprintf(stderr, "Memory overflow\n");
            fclose(fin);
            exit(0);
        }
        if (NULL == (curr_node2 = (node *) malloc(sizeof(node)))) {
            fprintf(stderr, "Memory overflow\n");
            fclose(fin);
            exit(0);
        }
        if (NULL == prev_node1) {
            *path1 = curr_node1;
        } else {
            prev_node1->next = curr_node1;
        }    
        if (NULL == prev_node2) {
            *path2 = curr_node2;
        } else {
            prev_node2->next = curr_node2;
        }            
        curr_node1->next = NULL;
        curr_node1->number = number1;
        curr_node2->next = NULL;
        curr_node2->number = number2;
        prev_node1 = curr_node1;
        prev_node2 = curr_node2;
        n_nodes += 1;
    }
    fclose(fin);
    return n_nodes;
}

//------------------------------------------------------------------------------

int read_node_coords( int nodes, char *filename, coord **coordsout )
{
    FILE *fin = fopen( filename, "r" );
    coord *coords = NULL;
    int id;
    double x, y;
    char junk[256];
    int n_nodes = 0;
    if( NULL == fin )
    {
        fprintf( stderr, "Unable to open %s\n", filename );
        exit(0);
    }

    if( NULL == (coords = (coord *)malloc( sizeof(coord)*nodes )) )
    {
        fprintf( stderr, "Memory overflow\n" );
        fclose(fin);
        exit(0);
    }

    fgets( junk, 255, fin );  // skip header
    int out;
    while( !feof(fin) )
    {
        if( (out = fscanf( fin, "%d,%lf,%lf", &id, &x, &y )) < 3 )
        {
            if( out != EOF )  fprintf( stderr, "Problem loading node coords.\n" );
            break;
        }
        if( n_nodes != id )
        {
            fprintf( stderr, "Problem loading node coords--Sorted expected.\n" );
            break;
        }

        coords[id].x = x;
        coords[id].y = y;

        n_nodes += 1;

//        if( (n_nodes % 1000) == 0 )  fprintf( stderr, "Loaded nodes: %d\n", n_nodes );
    }
    fclose( fin );

    *coordsout = coords;

    return  n_nodes;
}

//------------------------------------------------------------------------------

double get_distance( double x1, double y1, double x2, double y2 )
{
    double a2 = pow( x1-x2, 2.0 );
    double b2 = pow( y1-y2, 2.0 );

    return  sqrt( a2+b2 );
}

//------------------------------------------------------------------------------

double get_cost( int nodes, path_link *path, coord *coords )
{
    if( nodes < 2 )  return  0.0;

    double cost = 0.0;

    int c=0;
    for( ; c<nodes; c++ )
    {
        path_link *cp = path+c;
        int to = cp->to;
        if( to < 0 )  break;
        coord     *c1 = coords+(cp->from);
        coord     *c2 = coords+to;
        cost += get_distance( c1->x, c1->y, c2->x, c2->y );
    }

    return  cost;
}

//------------------------------------------------------------------------------

int compare_path_links_for_search(const void *p1, const void *p2)
{
//    char s1[256], s2[256];
//    path_link *plink1 = ((path_link *) p1);
//    path_link *plink2 = ((path_link *) p2);
//    // gross but works. 
//    sprintf(s1, "%06d,%06d", plink1->from, plink1->to);
//    sprintf(s2, "%06d,%06d", plink2->from, plink2->to);
//    return strcmp(s1, s2);

    const path_link *pl1 = (const path_link *)p1;
    const path_link *pl2 = (const path_link *)p2;

    // max and min, so either direction edge is same, and make test below easier.
    int lo1, hi1 = (pl1->from > pl1->to) ? (lo1=pl1->to, pl1->from) : (lo1=pl1->from, pl1->to);
    int lo2, hi2 = (pl2->from > pl2->to) ? (lo1=pl2->to, pl2->from) : (lo1=pl2->from, pl2->to);

    if( hi1 != hi2 )  return  (hi1 > hi2) - (hi1 < hi2);
      else  return  (lo1 > lo2) - (lo1 < lo2);
}

//------------------------------------------------------------------------------

void check_paths_disjoint(int path_size, path_link *p1, path_link *p2)
{
    path_link key;
    int i;
    sort_path_on_from(path_size, p1);
    for (i = 0; i < path_size; ++i) {
        key.from = p2[i].from;
        key.to = p2[i].to;
        if (NULL != bsearch(&key, p1, path_size, sizeof(path_link),
        compare_path_links_for_search)) {
            fprintf(stderr, "%d -> %d found in both path1 and path2\n", key.from, key.to);
        }
/* This has been dealt with in compare_path_links_for_search() */
//        key.to = p2[i].from;
//        key.from = p2[i].to;
//        if (NULL != bsearch(&key, p1, path_size, sizeof(path_link),
//        compare_path_links_for_search)) {
//            fprintf(stderr, "%d -> %d foundin both path1 and path2\n", key.from, key.to);
//        }
    }
}

//------------------------------------------------------------------------------

int main(int argc, char **argv)
{
    node *list1 = NULL, *list2 = NULL;
    int path_size;
    path_link *path1;
    path_link *path2;
    int err_bits;
    int check_disjoint;
    if( (argc != 2) && (argc !=3) ) {
        fprintf(stderr, "usage %s <csvfile> [<xy-csvfile>]\n", argv[0]);
        return 0;
    }
    if (0 >= (path_size = read_paths(argv[1], &list1, &list2))) {
        fprintf(stderr, "Path length = 0\n");
        return 0;
    }
    fprintf(stderr, "Nodes = %d\n", path_size); 
    node_list_to_path(path_size, list1, &path1);
    node_list_to_path(path_size, list2, &path2);
    err_bits = is_hamiltonian(path_size, path1);
    check_disjoint = !err_bits;
    if (err_bits & 1) {
        fprintf(stderr, "Not all nodes covered on path 1.\n");
    }
    if (err_bits & 1 << 1) {
        fprintf(stderr, "Some nodes visited more than once on path 1.\n");
    }
    if (err_bits & 1 << 2) {
        fprintf(stderr, "Incorrect node number found on path 1.\n");
    }
    err_bits = is_hamiltonian(path_size, path2);
    check_disjoint = check_disjoint && !err_bits;
    if (err_bits & 1) {
        fprintf(stderr, "Not all nodes covered on path 2.\n");
    }
    if (err_bits & 1 << 1) {
        fprintf(stderr, "Some nodes visited more than once on path 2.\n");
    }
    if (err_bits & 1 << 2) {
        fprintf(stderr, "Incorrect node number found on path 2.\n");
    }
    if (!check_disjoint) {
        check_paths_disjoint(path_size, path1, path2);
    }

    if( argc == 3 )
    {
        coord *coords = NULL;
        int nodes;
        nodes = read_node_coords( path_size, argv[2], &coords );
        if( nodes != path_size )
        {
            fprintf( stderr, "csvfile nodes != xy-csvfile nodes\n" );
            return 0;
        }

        fprintf( stderr, "Path 1 cost: %lf\n", get_cost( nodes, path1, coords ) );
        fprintf( stderr, "Path 2 cost: %lf\n", get_cost( nodes, path2, coords ) );
    }

    return  0;
}    
        
    
